package oct2013.linkednode;

public class ReorderList {
	public void reorderList(ListNode head) {
		if (head == null)
			return;
		ListNode t1 = head;
		ListNode t2 = head;
		while (t2 != null && t2.next != null) {
			t1 = t1.next;
			t2 = t2.next.next;
		}
		t2 = reverse(t1.next);
		t1.next = null;
		t1 = head;
		while (t2 != null) {
			ListNode tmp = t1.next;
			t1.next = t2;
			t1 = tmp;
			tmp = t2.next;
			t2.next = t1;
			t2 = tmp;
		}
	}

	ListNode reverse(ListNode head) {
		ListNode prev = null;
		ListNode cur = head;
		while (cur != null) {
			ListNode tmp = cur.next;
			cur.next = prev;
			prev = cur;
			cur = tmp;
		}
		return prev;
	}
}
